Bit Manipulation 🔄

Problems | LeetCode

Adding 1 to a number

Adding 1 to a number sets the rightmost unset bit and clears all the 1s to its right.

Adding 1 to a binary number causes binary addition with carry.

• Effect on the rightmost bits:
  • If the rightmost bit is 0, adding 1 turns it into 1. ✅
  • If the rightmost bit is 1, adding 1 causes a carry, flipping consecutive 1s to 0s until a 0 is encountered, which then becomes 1.

So, adding 1 actually sets the rightmost 0 bit to 1 and resets all the 1s to 0 that were to its right.

Operator

AND (&)

0 & 0 = 0
0 & 1 = 0
1 & 0 = 0
1 & 1 = 1

• 0 dominates – if any bit is 0, the result becomes 0.

• Keep specific bit: AND with a mask that has 1 only at the desired position so all other bits become 0.

  1101
  0100
   ^
  ----
  0100

• Check/Clear bit: AND with (1 << i) to check if the i-th bit is set, or AND with ~(1 << i) to clear that bit while keeping others unchanged.

  1101
  1011
   ^
  ----
  1001

OR (|)

0 | 0 = 0
0 | 1 = 1
1 | 0 = 1
1 | 1 = 1

• 1 dominates – if any bit is 1, the result becomes 1.

XOR (^)

0 ^ 0 = 0
0 ^ 1 = 1
1 ^ 0 = 1
1 ^ 1 = 0

• Same → 0, Different → 1
• XOR toggles the bit

0 ^ 0 = 0
1 ^ 0 = 1
---------
0 ^ 1 = 1
1 ^ 1 = 0

• XOR with 0 → keeps the bit same
• XOR with 1 → flips (toggles) the bit

XOR of numbers shows which bits differ

If two bits are different → result is 1, meaning that position is different.

5 ^ 5 = 0101 ^ 0101 = 0000  → no difference
5 ^ 4 = 0101 ^ 0100 = 0001  → difference at last bit

NOT (~)

~0 = 1
~1 = 0

• Flips every bit (0 → 1, 1 → 0).
• Also called bitwise complement.

Two’s Complement

One's Complement of x is ~x, So Two's complement is:

- x = (~x) + 1

Left Shift (<<)

Moves bits to the left.

a << n

• Means shift bits left by n positions.

5 << 1
00001010 = 10

Rule

x << n = x × 2ⁿ

Right Shift (>>)

Moves bits to the right.

a >> n

• Means shift bits right by n positions.

20 >> 1
00001010 = 10

Rule

x >> n = x / 2ⁿ

Operation

Set Bit

Goal:

0 → 1
1 → 1

AND

0 & 1 = 0
1 & 1 = 1

• Results depends on original bits

OR

0 | 1 = 1
1 | 1 = 1

• Results depends on mask bit

XOR

0 ^ 0 = 0
1 ^ 0 = 1
------
0 ^ 1 = 1
1 ^ 1 = 0

If the bit was already 1, xor turns it into 0(1 ^ 1 = 0)

Check Set Bit

Goal

• Target bit → unknown (0 or 1)
• Mask bit → fixed

AND

0 & 0 = 0
1 & 0 = 0
---------
0 & 1 = 0
1 & 1 = 1

Observation:

• If mask = 0, result is always 0 → cannot distinguish → eliminate.
• If mask = 1, result depends on the original bit.

So AND works if mask = 1.

OR

0 || 0 = 0
1 || 0 = 1
----------
0 || 1 = 1
1 || 1 = 1

Observation:

• If mask = 1, result always 1 → cannot distinguish.
• If mask = 0, result = original bit.

But we cannot isolate a specific bit using OR, because:

• All other bits also remain unchanged.
• OR does not zero out the other bits.

XOR

0 ^ 0 = 0
1 ^ 0 = 1
------
0 ^ 1 = 1
1 ^ 1 = 0

Observation:

• XOR changes the bit (toggle).
• It does not preserve the original value.

Clear Bit

Goal

0 → 0
1 → 0

0 dominates in AND operator.

Swapping Two Number

A = A ^ B
B = A ^ B = (A ^ B) ^ B = A ^ B ^ B = A
A = A ^ B = (A ^ B) ^ A = A ^ B ^ A = B

XOR of Range

• xor of two same number return 0 (a ⊕ a = 0)
• xor of any number with 0 return itself (a ⊕ 0 = a)

n	xor[0..n]	Calculation	Result
0	xor[0,0]	0	0
1	xor[0,1]	0 ⊕ 1	1
2	xor[0,2]	0 ⊕ 1 ⊕ 2	3
3	xor[0,3]	0 ⊕ 1 ⊕ 2 ⊕ 3	0
4	xor[0,4]	0 ⊕ 1 ⊕ 2 ⊕ 3 ⊕ 4	4
5	xor[0,5]	0 ⊕ 1 ⊕ 2 ⊕ 3 ⊕ 4 ⊕ 5	1
6	xor[0,6]	0 ⊕ 1 ⊕ 2 ⊕ 3 ⊕ 4 ⊕ 5 ⊕ 6	7
7	xor[0,7]	0 ⊕ 1 ⊕ 2 ⊕ 3 ⊕ 4 ⊕ 5 ⊕ 6 ⊕ 7	0
8	xor[0,8]	0 ⊕ 1 ⊕ 2 ⊕ 3 ⊕ 4 ⊕ 5 ⊕ 6 ⊕ 7 ⊕ 8	8

XOR from 0 to n

There’s a simple repeating pattern:

n % 4	xor(n)
0	n
1	1
2	n + 1
3	0

$$xor(l..r)=xor(r)⊕xor(l−1)$$

• Everything from 0 to l−1 appears twice and cancels out
• Only values from l to r remain

Number of Set Bit

Brian Kernighan’s Algorithm

Remove the rightmost set bit every iteration.

int countSetBits(int n) {
    int count = 0;

    while (n) {
        n = n & (n - 1);
        count++;
    }

    return count;
}

Lowest Set Bit / Right Most Bit

The rightmost 1 in the binary representation

It can be usefull to iterate through the bit efficiently

while(x){
    int bit = x & -x;
    cout << bit << endl;
    x -= bit;
}

Example:

x = 13 (1101)

lowest bit = 0001
next       = 0100
next       = 1000

Number of Set Bits in a Series (1...N)

Count set bits position by position using patterns in binary numbers.

Binary numbers repeat patterns every 2^k.

Dry Run (N = 5)

Decimal	Bit 2	Bit 1	Bit 0
1	0	0	1
2	0	1	0
3	0	1	1
4	1	0	0
5	1	0	1

Bit position 0

Pattern: 0 1 0 1 0 1
Set bits = 3

Bit position 1

Pattern: 0 0 1 1 0 0
Set bits = 2

Bit position 2

Pattern: 0 0 0 0 1 1
Set bits = 2

Total set bits: 3 + 2 + 2 = 7

int countSetBits(int n) {
    int total = 0;

    for (int i = 0; (1LL << i) <= n; i++) {
        int cycleLen = 1 << (i + 1); // 1 << i + 1 = 2^(i+1)

        // Count set bits in full cycles for bit 'i'
        int fullCycles = (n + 1) / cycleLen;
        total += fullCycles * (1 << i);

        // Count set bits in remaining part of the cycle
        int remainder = (n + 1) % cycleLen;
        total += (remainder > (1 << i)) ? (remainder - (1 << i)) : 0;
    }

    return total;
}

Loop runs while

2^i ≤ n

Iteration 1

i = 0

1 << i = 1 << 0 = 1

Cycle length:

cycleLen = 1 << (i + 1)
         = 1 << 1
         = 2

Full cycles

fullCycles = (n + 1) / cycleLen
           = (5 + 1) / 2
           = 3

Each cycle contributes:

1 << i = 1

So

total += 3 * 1 = 3

Remainder

remainder = (n + 1) % cycleLen
          = 6 % 2
          = 0

Extra bits:

remainder > 1 ? no

Total so far

total = 3

Iteration 2

i = 1

1 << i = 1 << 1 = 2

Cycle length

cycleLen = 1 << 2 = 4

Full cycles

fullCycles = 6 / 4 = 1

Contribution

total += 1 * 2 = 2

Total

total = 5

Remainder

remainder = 6 % 4 = 2

Check extra

remainder > 2 ? no

Total remains

5

Iteration 3

i = 2

1 << i = 1 << 2 = 4

Cycle length

cycleLen = 1 << 3 = 8

Full cycles

fullCycles = 6 / 8 = 0

Contribution

total += 0

Remainder

remainder = 6 % 8 = 6

Extra bits

6 > 4 → yes
extra = 6 - 4 = 2

Total

total = 5 + 2 = 7

Loop Ends

Next

1 << 3 = 8
8 > 5

Loop stops.

Final answer

7

Question

How computers store negative numbers

Computers store all data in binary (bits: 0 and 1). For signed integers, they use a system called: Two's Complement

Example (8-bit system)

Store +5

00000101

Store -5

Step 1: binary of 5

00000101

Step 2: invert bits

11111010

Step 3: add 1

11111011  ← this is -5

Why this works

Two’s complement allows:

• Simple addition/subtraction
• Same hardware for positive & negative
• No separate “sign handling”

Range of Data Types

The range depends on: Number of bits (n)

General Formula

For signed integers (two’s complement):

• Minimum = −2^(n−1)
• Maximum = 2^(n−1) − 1

Why range is asymmetric?

Example (8-bit):

• Range: −128 to +127

One extra negative value exists because:

• 00000000 = 0
• 10000000 = −128 (special case)